1. Field of the Invention
This invention relates generally to coded modulation techniques for use in digital communication systems. More particularly, the invention relates to methods and apparatus for the encoding and decoding multilevel coded and related codes such as serial and parallel concatenated coded signals. An improved hard iterative decoder is used to achieve near maximum likelihood performance at a much lower computational cost.
2. Description of the Related Art
Multi-level coding (MLC), devised by Imia and Hirakawa, and later studied and applied by many others in the literature, is a powerful coded modulation technique for bandwidth limited channels (see the reference list provided in the attached IDS for the key prior art referred to herein). MLC schemes employ individual (binary) component codes to protect each information bit. Staring from a high power low rate code for least significant bits (LSB) i.e. the lowest level, MLC schemes lower the code power (and increases the rate) as they move to higher level bits. The most significant bits (MSB) i.e. the highest level, are either kept uncoded or use the lowest power high rate code. The coded bits are then mapped on to a constellation point as illustrated in FIG. 1. MLC, in contrast to Ungerboeck's trellis coded modulation (TCM), provides flexibility in the code rate selection at each level. Various types of codes like block codes, convolutional codes, turbo codes and the like can be employed as component codes at each level. In addition, MLC schemes can be decoded using a simple multi stage decoding (MSD) where the codes are individually decoded.
MSD of MLC has been documented and analyzed in the literature. MSD starts decoding at the first level and moves up one level at a time using the knowledge of the coded bits that have already been decoded. In the first level, the coded bits at all higher levels are assumed to be equiprobable, and hence, the first level suffers from a high path multiplicity. In order to overcome these drawbacks of MLC, interleaving between levels and iterations among levels have been proposed. Interleaving spreads out errors that occur in any code with respect to all other codes and reduces the chances of error propagation. Hard iterations have been proposed where hard decoding decisions from a previous MSD run are used in a next MSD run. It has been shown in the literature that such MSD iterations along with interleaving can reduce the impact of path multiplicity thereby improving performance.
Huber et al. have shown that MSD is sufficient to decode MLCs and to approach capacity if the code rates at each level are selected according to the capacity rule. However, MLC schemes designed according to the capacity rule may not achieve the optimum error coding exponent especially for shorter block lengths. Also, it is known that the MLC schemes designed according to the capacity rule have excellent performance over known channels, however, their performance suffer in presence of channel variations. Of particular interest to the present invention is the case where MLC schemes are designed to achieve the same minimum Euclidean distance at all coding levels. This rule that maintains the same minimum distance and targets similar performances at all levels is called the balance distances rule. In general the MLC schemes designed according to the balance distances rule can achieve channel capacity with optimal decoding using overall maximum likelihood (ML) decoding. However, such a ML receiver that operates on the hybrid trellis is impractical due to the large number of states on the hybrid trellis.
Methods have been developed that employ hard iterative decoding to further improve decoding of MLCs by reducing or eliminating the additional path multiplicity that is not resolved by the MSD. So far in the literature, iterations have been discussed for a pre-selected number of iterations. The acceptable number of iterations depends on the component codes, constellation mapping policy and on the value of the signal to noise ratio (SNR). Iterating with a pre-selected number of iterations is an ad-hoc approach and is suboptimal.
On the other hand, iterating with a terminating policy is the optimal way to run iterations thereby reaching a target solution with a minimum number of iterations. Lacking from the prior art is such a termination policy. It would be desirable to have such a termination policy and to use it to construct an improved hard iteration decoding (IHID) algorithm. Also desirable would a list Viterbi IHID (LV-IHID) algorithm, which employs list Viterbi decoding to widen the range of SNR values where the IHID algorithm can provide near-ML performance. More generally, it would be desirable to have a class of methods and apparatuses that could use multiple instances of the IHID algorithm, starting from multiple starting points, to terminate on multiple candidate termination points, the best of which being used to select a highly probable candidate solution that performs statistically similarly to the maximum likelihood solution.